package x.y.z;

public class Interview_2_7_Intersection {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Result resultA = getTailAndSize(headA);
        Result resultB = getTailAndSize(headB);
        if (resultA.tail != resultB.tail) {
            return null;
        }

        ListNode shorter = resultA.size > resultB.size ? headB : headA;
        ListNode longer = resultA.size > resultB.size ? headA : headB;
        longer = getKthNode(longer, Math.abs(resultA.size - resultB.size));
        while (shorter != longer) {
            shorter = shorter.next;
            longer = longer.next;
        }
        return longer;
    }

    private Result getTailAndSize(ListNode node) {
        if (node == null) {
            return null;
        }
        int size = 1;
        ListNode cur = node;
        while (cur.next != null) {
            size++;
            cur = cur.next;
        }
        return new Result(size, cur);
    }

    private ListNode getKthNode(ListNode node, int k) {
        ListNode cur = node;
        while (k > 0 && cur != null) {
            cur = cur.next;
            k--;
        }
        return cur;
    }
}

class Result {
    int size;
    ListNode tail;

    public Result(int size, ListNode tail) {
        this.size = size;
        this.tail = tail;
    }
}
